package sort;

/**
 * 希尔排序，插入排序的改进版，时间复杂度和使用的序列有关, 是不稳定的排序
 */
public class ShellSort {

    /**
     * 希尔增量序列：时间复杂度N^2 Hibbard序列： 最坏时间复杂度 N^(3/2) 平均复杂度 N^(5/4) Sedgewick序列: 最坏时间复杂度
     * N^(4/3) 平均复杂度 N^(7/6)
     */
    public enum Sequence {
        ShellIncrement, Hibbard, Sedgewick
    }

    /**
     * 希尔排序
     * 
     * @param <E>      实现了comparable接口的泛型
     * @param array    待排序数组
     * @param sequence 希尔排序使用的序列， 有Sequence.ShellIncrement, Sequence.Hibbard, Squence.SedgeWick
     */
    public static <E extends Comparable<E>> void sort(E[] array, Sequence sequence) {
        if (sequence == Sequence.ShellIncrement) {
            for (int D = array.length / 2; D > 0; D/=2) {
                insertSort(array, D);
            }
        }if (sequence == Sequence.Hibbard){
            int D = (int)(Math.log(array.length)/Math.log(2));
            if (D % 2 == 0){
                D = D + 1;
            }
            for (; D > 0; D-=2){
                insertSort(array, D);   
            }
        }
    }

    private static <E extends Comparable<E>> void insertSort(E[] array, int interval) {
        for (int i = interval; i < array.length; i += interval) {
            int k = i;
            E tmp = array[i];
            for (int j = i - interval; j >= 0 && tmp.compareTo(array[j]) < 0; j -= interval) {
                array[j + interval] = array[j];
                k = j;
            }
            array[k] = tmp;
        }
    }
}